package william.array;

/**
 * @author ZhangShenao
 * @date 2024/1/29
 * @description <a href="https://leetcode.cn/problems/sort-colors/description/">...</a>
 */
public class Leetcode75_颜色分类_计数排序 {
    /**
     * 采用计数排序思想(数据样本量很小,只有3种元素)
     * 创建一个长度为3的数组counts,维护每个元素出现的次数,counts[i]为元素i出现的次数
     * 遍历nums数组,更新counts数组
     * 再次遍历counts数组,按照元素和次数依次写回nums数组
     * <p>
     * 时间复杂度O(N) 需要遍历nums两次
     * 空间复杂度O(1) counts数组需要固定3个额外空间
     */
    public void sortColors(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 2) {
            return;
        }

        //维护counts计数数组
        int[] counts = new int[3];
        for (int n : nums) {
            counts[n]++;
        }

        //遍历counts数组,按照元素和次数依次写回nums数组
        int i = 0;
        for (int j = 0; j < 3; j++) {
            int count = counts[j];
            for (int k = 0; k < count; k++) {
                nums[i++] = j;
            }
        }
    }

    /**
     * 将数组nums中i和j两个下标处的元素进行交换
     */
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
